package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2021/1/1 下午11:15
 */
public class _01_背包问题_01 {

    private static int knapsack(int[] weights,int[] values, int bag) {

        if (bag <= 0 || weights == null || weights.length == 0) {
            return 0;
        }

        int[][] dp = new int[weights.length][bag + 1];

        for (int i = 0; i < dp.length; i++) {

            for (int j = 0; j < dp[i].length; j++) {

                dp[i][j] = -1;
            }
        }

        knapsack(weights,values,bag,weights.length - 1, dp);

        for (int i = 0; i < dp.length; i++) {

            System.out.println(Arrays.toString(dp[i]));
        }

        return dp[weights.length - 1][bag];
    }

    private static int knapsack(int[] weights,int[] values, int rest, int index,int[][] dp) {

        if (index  == -1) {

            return 0;
        }

        if (dp[index][rest] != -1) {

            return dp[index][rest];
        }

        //        // 不装 index
        int noIndex = knapsack(weights,values,rest,index - 1,dp);

        int haveIndex = 0;
        if (rest >= weights[index]) {
            // 装 index
            haveIndex = knapsack(weights,values, rest - weights[index],index - 1, dp) + values[index];
        }

        int max = Math.max(noIndex, haveIndex);
        dp[index][rest] = max;

        return max;
    }

//    private static int knapsack(int[] weights,int[] values, int rest, int index,int[][] dp) {
//
//        if (index >= weights.length) {
//
//            return 0;
//        }
//
//        if (dp[index][rest] != -1) {
//
//            return dp[index][rest];
//        }
//
//
//        // 不装 index
//        int noIndex = knapsack(weights,values,rest,index + 1,dp);
//
//        int haveIndex = 0;
//        if (rest >= weights[index]) {
//            // 装 index
//            haveIndex = knapsack(weights,values, rest - weights[index],index + 1, dp) + values[index];
//        }
//
//        int max = Math.max(noIndex, haveIndex);
//        dp[index][rest] = max;
//        return max;
//    }

    public static void main(String[] args) {

        /**
         * 	    0  1  2  3  4  5  6  7  8   9  10
         * 2:6	[0, 0, 6, 6, 6, 6, 6, -1, 6, -1, 6]
         * 2:3	[0, 0, -1, -1, 9, 9, 9, -1, -1, -1, 9]
         * 6:5	[-1, 0, -1, -1, -1, 9, 9, -1, -1, -1, 14]
         * 5:4	[-1, -1, -1, -1, -1, -1, 9, -1, -1, -1, 14]
         * 4:6	[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15]
         */

        int maxValue = knapsack(new int[]{2, 2, 6, 5, 4}, new int[]{6, 3, 5, 4, 6}, 10);

        System.out.println(maxValue);

    }

}
